package org.trc.network;

import java.io.File;
import java.io.IOException;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.PriorityQueue;

import javax.swing.JFileChooser;

import org.geotools.data.DataUtilities;
import org.geotools.data.DefaultTransaction;
import org.geotools.data.Transaction;
import org.geotools.data.shapefile.ShapefileDataStore;
import org.geotools.data.shapefile.ShapefileDataStoreFactory;
import org.geotools.data.shapefile.shp.ShapefileException;
import org.geotools.data.simple.SimpleFeatureCollection;
import org.geotools.data.simple.SimpleFeatureSource;
import org.geotools.data.simple.SimpleFeatureStore;
import org.geotools.feature.FeatureCollections;
import org.geotools.feature.SchemaException;
import org.geotools.feature.simple.SimpleFeatureBuilder;
import org.geotools.referencing.CRS;
import org.geotools.referencing.crs.DefaultGeographicCRS;
import org.geotools.swing.data.JFileDataStoreChooser;
import org.opengis.feature.simple.SimpleFeature;
import org.opengis.feature.simple.SimpleFeatureType;
import org.opengis.referencing.FactoryException;
import org.opengis.referencing.NoSuchAuthorityCodeException;
import org.trc.network.Node;

import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LineString;

public class RoutePlanning {
	private Network network;
	private Path shortestPath; //Node序列
	private ArrayList<Edge> route; //Edge序列
	
	public RoutePlanning(Network network){
		this.network = network;
	}
	
	/**
	 * 节点优先级队列的比较器
	 */
	private static Comparator<DijkstraNode> comparator = new Comparator<DijkstraNode>() {
		public int compare(DijkstraNode n1, DijkstraNode n2) {
			return (n1.cost < n2.cost ? -1 : n1.cost > n2.cost ? 1 : 0);
		}
	};
	
	/**
	 * Dijkstra算法 -- 点到点
	 * 
	 * @param startNode
	 * @param endNode
	 */
	public boolean computeFastestWay(Node startNode, Node endNode){
		//Initialization
		DijkstraNode curDJNode= new DijkstraNode(startNode, 0); //current expanding node
		curDJNode.setPreNode(null);
		PriorityQueue<DijkstraNode> cadidateNodeQueue = new PriorityQueue<DijkstraNode>(10, comparator); //备选节点
		HashSet<String> nodeLabeld = new HashSet<String>();// 已标号的节点	
		HashSet<String> nodeVisited = new HashSet<String>();// 已加入优先级对列的节点
		
		//choose and expand
		Node adjNode = null;
		DijkstraNode adjDJNode = null;
		
		while( curDJNode != null && !curDJNode.node.equals(endNode) ){
			nodeLabeld.add(curDJNode.node.id);
			for(String adjNodeId : curDJNode.node.getAdjNodes()){//扩展：对于当前搜索节点的每一个邻节点，判断状态
				adjNode = this.network.getNodeById(adjNodeId);
				if(nodeLabeld.contains(adjNodeId)){//永久标号
					continue;
				}else if(!nodeVisited.contains(adjNodeId)){//未到达
					adjDJNode = new DijkstraNode(adjNode, curDJNode.cost + curDJNode.node.getAdjEdgeWeight(adjNodeId));					
					adjDJNode.setPreNode(curDJNode);
					cadidateNodeQueue.add(adjDJNode);
					nodeVisited.add(adjNodeId);
				}else {//临时标号
					for (DijkstraNode djNode : cadidateNodeQueue) {//在备选集中找到该对象
						if (djNode.node.equals(adjNode)) {
							adjDJNode = djNode;
							break;
						}
					}
					if (curDJNode.cost + curDJNode.node.getAdjEdgeWeight(adjNodeId)< adjDJNode.cost) {
						cadidateNodeQueue.remove(adjDJNode);
						adjDJNode.updateLabel(curDJNode.cost + curDJNode.node.getAdjEdgeWeight(adjNodeId));
						adjDJNode.setPreNode(curDJNode);
						cadidateNodeQueue.add(adjDJNode);
					}
			    }
			}
//			System.out.println(curDJNode.node.id);
			curDJNode = cadidateNodeQueue.poll();	
		}
		
		if(curDJNode != null){
			this.shortestPath = this.computeResultPath(curDJNode); //Node 序列
			this.route = this.computeRoute(); //Edge 序列
		    //System.out.println("Shortest path computaiton is completed");
		    return true;
        }
		else {
			this.shortestPath = null;
			System.out.println("There is no path between O-D");
			return false;
		}
	}
	
	/**
	 * Dijkstra算法 -- 任意两点
	 * 
	 * Direct :  1 : 双向  ; 2：顺方向  ; 3：逆方向 （数字化方向）
	 * offset : 已数字化起点作为参考点
	 * 
	 * @param fromEdge 起始边
	 * @param offset1  起始点偏移
	 * @param direct1 行车方向
	 * 
	 * @param toEdge 终点边 
	 * @param offset2 终点偏移
	 * @param direct2 行车方向
	 * @return
	 */
	public boolean computeFastestWay(Edge fromEdge, float offset1, int direct1,  Edge toEdge, float offset2, int direct2){
		//构建虚拟的起始点
		Node vStartNode = new Node("vStartNode", null);
		Edge vStartEdge1 = new Edge("vStartEdge1", vStartNode.id, fromEdge.endNodeID, 2, (float) (fromEdge.length - offset1), fromEdge.line);
		Edge vStartEdge2 = new Edge("vStartEdge2", vStartNode.id, fromEdge.startNodeID, 2, offset1, fromEdge.line);
		
		if(direct1 == 1) {
			vStartNode.addEdge(vStartEdge1);
		    vStartNode.addEdge(vStartEdge2);		    
		}else if (direct1 == 2){			
			vStartNode.addEdge(vStartEdge1);;			
		}else if (direct1 == 3){					
			vStartNode.addEdge(vStartEdge2);			
		}
		
		//构建虚拟的结束点
		Node vEndNode = new Node("vEndNode", null);	
		Edge vEndEdge1 = new Edge("vEndEdge1", toEdge.startNodeID, vEndNode.id, 2, offset2, toEdge.line);
		Edge vEndEdge2 = new Edge("vEndEdge2", toEdge.endNodeID, vEndNode.id, 2, (float) (toEdge.length - offset2), toEdge.line);
		
		Node toEdgeStartNode = network.getNodeById(toEdge.startNodeID);	
		Node toEdgeEndNode = network.getNodeById(toEdge.endNodeID);
		
		if(direct2 == 1) {	
			toEdgeStartNode.addEdge(vEndEdge1);	    
			toEdgeEndNode.addEdge(vEndEdge2);		    
		}else if (direct2 == 2){			
			toEdgeStartNode.addEdge(vEndEdge1);	 			 
		}else if (direct2 == 3){			
			toEdgeEndNode.addEdge(vEndEdge2);			
		}
	
		//Initialization
		DijkstraNode curDJNode= new DijkstraNode(vStartNode, 0); //current expanding node		
		curDJNode.setPreNode(null);		
		PriorityQueue<DijkstraNode> cadidateNodeQueue = new PriorityQueue<DijkstraNode>(10, comparator); //备选节点		
		HashSet<String> nodeLabeld = new HashSet<String>();// 已标号的节点			
		HashSet<String> nodeVisited = new HashSet<String>();// 已加入优先级对列的节点
		
		//choose and expand
		Node adjNode = null;	
		DijkstraNode adjDJNode = null;		
		while(curDJNode != null && !curDJNode.node.id.equals("vEndNode")){		
			nodeLabeld.add(curDJNode.node.id);			
			for(String adjNodeId : curDJNode.node.getAdjNodes()){//扩展：对于当前搜索节点的每一个邻节点，判断状态
				if(adjNodeId.equals("vEndNode"))
					adjNode = vEndNode;
				else
				    adjNode = this.network.getNodeById(adjNodeId);
				if(nodeLabeld.contains(adjNodeId)){//永久标号
					continue;
				}else if(!nodeVisited.contains(adjNodeId)){//未到达
					adjDJNode = new DijkstraNode(adjNode, curDJNode.cost + curDJNode.node.getAdjEdgeWeight(adjNodeId));					
					adjDJNode.setPreNode(curDJNode);
					cadidateNodeQueue.add(adjDJNode);
					nodeVisited.add(adjNodeId);
				}else {//临时标号
					for (DijkstraNode djNode : cadidateNodeQueue) {//在备选集中找到该对象
						if (djNode.node.equals(adjNode)) {
							adjDJNode = djNode;
							break;
						}
					}
					if (curDJNode.cost + curDJNode.node.getAdjEdgeWeight(adjNodeId)< adjDJNode.cost) {
						cadidateNodeQueue.remove(adjDJNode);
						adjDJNode.updateLabel(curDJNode.cost + curDJNode.node.getAdjEdgeWeight(adjNodeId));
						adjDJNode.setPreNode(curDJNode);
						cadidateNodeQueue.add(adjDJNode);
					}
			    }
			}
			//System.out.println(curDJNode.node.id);
			curDJNode = cadidateNodeQueue.poll();		
		}
		
		if(curDJNode != null){
			this.shortestPath = this.computeResultPath(curDJNode);
			this.route =  this.computeRoute();
			
			if(((Node)this.shortestPath.get(1)).id.equals(fromEdge.endNodeID)) //处理起始边
				route.set(0, vStartEdge1);
			else
				route.set(0, vStartEdge2);
			
			if(((Node)this.shortestPath.get(shortestPath.size()- 2)).id.equals(toEdge.startNodeID)){//处理结束边
				route.set(route.size()-1, vEndEdge1);
				toEdgeStartNode.removeVirtualAdjEdge(); //移除加入的虚拟点的拓扑关系
			}
			else {
				route.set(route.size()-1, vEndEdge2);
				toEdgeEndNode.removeVirtualAdjEdge(); //移除加入的虚拟点的拓扑关系
			}
			
 		    //System.out.println("Shortest path computaiton is completed");
		    		    
		    return true;
		    
		}else {
			
			this.shortestPath = null;
			
			System.out.println("There is no path between O-D");
			
			return false;
		}
		
		//TODO: 移除加入的虚拟点的拓扑关系
	}
	
	public boolean computeFastestWay(String fromEdgeID, float offset1, int direct1,  String toEdgeID, float offset2, int direct2){
		Edge fromEdge = this.network.getEdgeById(fromEdgeID);
		Edge toEdge = this.network.getEdgeById(toEdgeID);
		return this.computeFastestWay(fromEdge, offset1, direct1, toEdge, offset2, direct2);	
	}

	/**
	 *  返回路径
	 *  
	 * @return
	 */
	public ArrayList<Edge> getRoute(){
		return this.route;
	}
	
	public Path getPath(){
		return this.shortestPath;
	}

    /**
     *  返回路径长度
     *  
     * @return
     */
	public float getRouteLength(){
		if(this.route == null)
			return Float.MAX_VALUE;
		float length = 0f;
		for(Edge edge : route)
			length += edge.length;
		return length;
	}
	
	/**
	 * 获取Shapefile输出
	 * 
	 * @throws IOException 
	 * @throws SchemaException 
	 * @throws FactoryException 
	 * @throws NoSuchAuthorityCodeException 
	 */
	public void getShapefileOutput() throws IOException, SchemaException, NoSuchAuthorityCodeException, FactoryException{
		if(this.shortestPath == null)
			return;
		JFileDataStoreChooser chooser = new JFileDataStoreChooser("shp");	
	    chooser.setDialogTitle("Save a new shapefile");
	    chooser.setSaveFile(new File("D:\\"));
        if (chooser.showSaveDialog(null) != JFileChooser.APPROVE_OPTION) {
            return;
        }
        File outputShapefile = chooser.getSelectedFile();
     
		ShapefileDataStoreFactory dataStoreFactory = new ShapefileDataStoreFactory();
		
		Map<String, Serializable> params = new HashMap<String, Serializable>();
		params.put("url", outputShapefile.toURI().toURL());
		params.put("create spatial index", Boolean.TRUE);
		
		ShapefileDataStore writeDataStore = (ShapefileDataStore) dataStoreFactory.createNewDataStore(params);

		// specify the feature type
		final SimpleFeatureType TYPE = DataUtilities.createType(
				"RoadSegment",
				"GEOM:MultiLineString:srid=4326," 
			    + "LINKID:String,"
				+ "NUM:int"); //+ "DIRECTION:int,"

		writeDataStore.createSchema(TYPE);
		//writeDataStore.forceSchemaCRS(CRS.decode("EPSG:4365", true));
		writeDataStore.forceSchemaCRS(DefaultGeographicCRS.WGS84);

		//prepare new feature collection	
		SimpleFeatureCollection collection = FeatureCollections.newCollection();
		SimpleFeatureBuilder featureBuilder = new SimpleFeatureBuilder(TYPE);

		SimpleFeature feature = null;
		
		ArrayList <Edge> edges = this.getRoute();
		
		float length = this.getRouteLength();
		
		int i = 1;
		
		for (Edge edge : edges) {
			// create feature	
			featureBuilder.add(new GeometryFactory().createMultiLineString(new LineString[]{edge.line}));
			featureBuilder.add(edge.id);
			featureBuilder.add(i++);
			feature = featureBuilder.buildFeature(null);
			collection.add(feature);
		}

		//create transaction
		Transaction transaction = new DefaultTransaction("create");
		String typeName = writeDataStore.getTypeNames()[0];
		SimpleFeatureSource featureSource = writeDataStore.getFeatureSource(typeName);

		if (featureSource instanceof SimpleFeatureStore) {
			SimpleFeatureStore featureStore = (SimpleFeatureStore) featureSource;
			featureStore.setTransaction(transaction);
			try {
				featureStore.addFeatures(collection);
				transaction.commit();
			} catch (Exception problem) {
				problem.printStackTrace();
				transaction.rollback();
			} finally {
				transaction.close();
			}
			System.exit(0); // success!
		} else {
			System.out.println(typeName + " does not support read/write access");
			System.exit(1);
		}
		
	}
	
	/**
     * 回溯目的点，获取路径
     */
	private Path computeResultPath(DijkstraNode destinationNode){
		Path path = new Path();
		path.add(destinationNode.node);
		while(destinationNode.preNode != null){
			path.add(destinationNode.preNode.node);
			destinationNode = destinationNode.preNode;
		}
		path.reverse();
		return path;
	}
	
	/**
	 * 
	 * 利用节点的Path路径，计算Edge的序列
	 * 
	 * @return
	 */
	private ArrayList<Edge> computeRoute(){
		if(this.shortestPath == null)
			return null;
		ArrayList<Edge> edgeList = new ArrayList<Edge> ();
		ArrayList <String> edgeIdList = (ArrayList <String>)this.shortestPath.getEdges();
		for(String edgeID : edgeIdList) {
			edgeList.add(this.network.getEdgeById(edgeID));
		}
		return edgeList;
	}

	//节点包装类
	private static class DijkstraNode {
		public Node node;	
	    public double cost = Double.MAX_VALUE; //点标号
	    public DijkstraNode preNode = null;//直接前驱节点
	    
//	    public int status = 0; //三种状态：未到达(0)、临时标号(1)、永久标号(2)
//	    private static final int isVisited = 1;
//	    private static final int isLabeled = 2;

		public DijkstraNode(Node node, double cost) {
			this.node = node;
			this.cost = cost;
		}
		
	    public void updateLabel(double value){
	    	this.cost = value;
	    }
	    
	    public void setPreNode(DijkstraNode node){
	    	this.preNode = node;
	    } 
	  
	}
	
    public static void main(String[] args) throws IOException, ShapefileException, NoSuchAuthorityCodeException, SchemaException, FactoryException {
    	//Network network = new Network("E:\\Data\\Road\\Wuhan_2010.9\\RWuhan45_polyline_EPSG32650.shp", null);
    	
    	Network network = new Network("E:\\Data\\Road\\Wuhan_2010.9\\WuhanMainRoad_3rd_PATHNAME_wuchang5.shp", true);
    	RoutePlanning rp = new RoutePlanning(network);
    	
    	//rp.computeFastestWay(network.getNodeById("45546200955"), network.getNodeById("45546201042"));
    	if(rp.computeFastestWay(network.getNodeById("45546216089"), network.getNodeById("5546200263")))
    		rp.getShapefileOutput();
    	
/*    	if(rp.computeFastestWay("27", 577.5f, 2, "29", 202f, 2))
    		//rp.getShapefileOutput();
    		System.out.println(rp.getRouteLength());*/
    	
    	//rp.computeFastestWay(network.getEdgeById("45546200403"), network.getEdgeById("45547202947"));
/*    	for(Object node : rp.shortestPath){
    		Node dd = (Node)node;
    		System.out.println("The path is following:");
    		System.out.println(dd.id);
    	}*/
    }

}
